// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 9：
// 假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
//
//        perm[i] 能够被 i 整除
//        i 能够被 perm[i] 整除
//        给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
//
//        示例 1：
//
//        输入：n = 2
//        输出：2
//        解释：
//        第 1 个优美的排列是 [1,2]：
//        - perm[1] = 1 能被 i = 1 整除
//        - perm[2] = 2 能被 i = 2 整除
//        第 2 个优美的排列是 [2,1]:
//        - perm[1] = 2 能被 i = 1 整除
//        - i = 2 能被 perm[2] = 1 整除
//        示例 2：
//
//        输入：n = 1
//        输出：1
//
//
//        提示：
//
//        1 <= n <= 15

// 解题思路：
// 画决策树，每次选一个数字，并且标记
// 选下一个数字，如果数字被标记过，就不选，否则进行标记
// 返回本层的时候，取消标记
// 当到达第 n + 1 个数字的时候，收集结果

public class CountArrangement {
    int ret = 0;
    boolean[] check;
    public int countArrangement(int n) {
        check = new boolean[n + 1];
        dfs(n, 1);
        return ret;
    }
    public void dfs(int n, int pos){
        if(pos == n + 1){
            ret++;
            return;
        }
        for(int i = 1; i <= n; i++){
            if((i % pos == 0 || pos % i == 0) && check[i] == false){
                check[i] = true;
                dfs(n, pos + 1);
                check[i] = false;
            }
        }
    }
}
